#include<time.h>
#include<stdlib.h>
#include<stdbool.h>
#include<stdio.h>
#include <string.h>

#include <limits.h>

#define IMAX(a, b) ((a)>(b)?(a):(b))

void bucket_sort(int* nums, int length)
{
    if (nums == NULL || length < 2) return;
    int imax = INT_MIN;
    int i = 0;
    for (; i < length; i++) {
        imax = IMAX(imax, nums[i]);
    }

    int *bucket = (int*)malloc((imax + 1)*sizeof(int));
    memset(bucket, 0, (imax + 1)*sizeof(int));
    if (bucket == NULL) return;
    for (i = 0; i < length; i++) {
        bucket[nums[i]]++;
    }
    i = 0;
    for (int j = 0; j < (imax + 1); j++) {
        while (bucket[j]-- > 0) {
            nums[i++] = j;
        }
    }
    if (bucket != NULL) free(bucket);
    bucket = NULL;
    return;
}

//for test
int comp(const void*a,const void*b)//用来做比较的函数，从小到大。
{
    return *(int*)a-*(int*)b;
}
// qsort(a,n,sizeof(int),comp);//调用qsort排序, n数组长度
//for test
int * generate_random_array(int max_size, int max_value, int *reallength) 
{
        srand((unsigned)time(NULL));
        int length = rand() % (max_size + 1); //生成0~maxSize+1的随机数
        *reallength = length;
        int *arr = (int*)malloc(length * sizeof(int));  
        for (int i = 0; i < length; i++) {
//            arr[i] = (rand() % (max_value + 1)) - (rand() % max_value);
            arr[i] = rand() % (max_value + 1); //由于桶排序跟具体的数据状况有关，这里生成的数组值只包括正数
        }
        return arr;
}
//for test
int* copy_array(int arr[], int length) 
{
        if (length == 0) {
            return NULL;
        }
        int *res = (int *)malloc(length * sizeof(int));
        for (int i = 0; i < length; i++) {
            res[i] = arr[i];
        }
        return res;
}
//for test
bool is_equal(int arr1[], int length1, int arr2[], int length2) 
{
    if ((length1 == 0 && length2 != 0) || (length1 != 0 && length2 == 0)) {
        return false;
    }
    if (length1 == 0 && length2 == 0) {
        return true;
    }
    if (length1 != length2) {
        return false;
    }
    for (int i = 0; i < length1; i++) {
        if (arr1[i] != arr2[i]) {
            return false;
        }
    }
    return true;
}
//for test
void print_array(int arr[], int length) {
    if (length == 0) {
        return;
    }
    for (int i = 0; i < length; i++) {
        printf("%d  ", arr[i]);
    }
    printf("\n");
}

void main(int argc, char **argv) {
    int test_time = 500000;
    int max_size = 100;
    int max_value = 150;
    bool succeed = true;
    int *arr1 = NULL;
    int *arr2 = NULL;
    int *arr3 = NULL;
    int reallength = 0;
    for (int i = 0; i < test_time; i++) {
        arr1 = generate_random_array(max_size, max_value, &reallength);
        arr2 = copy_array(arr1, reallength);
        arr3 = copy_array(arr1, reallength);
        bucket_sort(arr1, reallength);
        qsort(arr2, reallength , sizeof(int),comp);
        if (!is_equal(arr1, reallength, arr2, reallength)) {
            succeed = false;
            break;
        }
       if (arr1 != NULL) free(arr1); 
       if (arr2 != NULL) free(arr2); 
       if (arr3 != NULL) free(arr3);
        arr1 = NULL; arr2 = NULL; arr3 = NULL;
    }
    printf("%s\n", succeed ? "Nice!" : "Fucking fucked!");
    if (succeed == false) {
        printf("insertsort\n");
        print_array(arr1,reallength) ;
        printf("qsort\n");
        print_array(arr2, reallength);
        printf("raw\n");
        print_array(arr3, reallength);
    }

}
